import functools
class Solution(object):
    def numberOfWays(self, startPos, endPos, k):
        base = 10 ** 9 + 7
        @functools.cache
        def dfs(t, n):
            if n == 0:
                if t == startPos:
                    return 1
                else:
                    return 0
            else:
                return (dfs(t + 1, n - 1) + dfs(t - 1, n - 1) ) % base

        return dfs(endPos, k)
